/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-28
 * Time: 22:23
 */
public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap(){
        this.elem = new int[10];//创建一个数组
    }

    //建堆，按照大根堆来建立
    public void creativeHeap(int [] array){
        for(int i =0;i<array.length;++i){
            this.elem[i] = array[i];
            this.usedSize++;
        }

        for(int p =(this.usedSize-1-1)/2;p>=0;p--){
            shiftDown(p,this.usedSize);
        }

    }
    public void swap(int[] elem,int i,int j){
           int tmp = this.elem[i];
           this.elem[i] = this.elem[j];
           this.elem[j] = tmp;
    }

    public void shiftDown(int root,int len){
        int parent = root;
        int child = 2*parent+1;//跟的左孩子
        while(child<len){
            //找到孩子节点最大的
            if(child+1 < len&&this.elem[child]<this.elem[child+1]){
                 child++;
            }
            //此时child是最大的，孩子最大的要与parent交换
            if(this.elem[parent]<this.elem[child]){
                //如果父母比孩子小那就交换
               swap(this.elem,child,parent);
               parent = child;
               child= 2*parent+1;
            }else {
                break;
            }
        }
    }





}
